package leetcode_400;

/**
 *@author 周杨
 *RotateFunction_396 返回一个数组的旋转数组的坐标元素乘积和
 *describe:用递推式 AC 100%
		F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1]
		F(k-1) = 0 * Bk-1[0] + 1 * Bk-1[1] + ... + (n-1) * Bk-1[n-1]
		       = 0 * Bk[1] + 1 * Bk[2] + ... + (n-2) * Bk[n-1] + (n-1) * Bk[0]
		Then,
		
		F(k) - F(k-1) = Bk[1] + Bk[2] + ... + Bk[n-1] + (1-n)Bk[0]
		              = (Bk[0] + ... + Bk[n-1]) - nBk[0]
		              = sum - nBk[0]
		Thus,
		
		F(k) = F(k-1) + sum - nBk[0]
		What is Bk[0]?
		
		k = 0; B[0] = A[0];
		k = 1; B[0] = A[len-1];
		k = 2; B[0] = A[len-2];
		...
 *2018年7月15日 下午1:51:17
 */
public class RotateFunction_396 {
	public int maxRotateFunction(int[] A) {
		int allSum = 0;
		int len = A.length;
		int F = 0;
		for (int i = 0; i < len; i++) {
		    F += i * A[i];
		    allSum += A[i];
		}
		int max = F;
		for (int i = len - 1; i >= 1; i--) {
		    F = F + allSum - len * A[i];
		    max = Math.max(F, max);
		}
		return max;   
	}
}
